#include <stdio.h>

void shellsort(int *a, int n)
{
    int m = n/2, i, j, k, t;

    while (m > 1) {
        for (i = 0; i < m; i++) {
             for (j = i; j < n; j += m) {
                t = a[j];
                for (k = j; k > i && a[k-m] > t; k -= m)
                    a[k] = a[k-m];
                a[k] = t;
             }
        }
        m = (m-1)/2;
    }

    for (i = 1; i < n; i++) {
        t = a[i];
        for (j = i; j > 0 && a[j-1] > t; j--)
            a[j] = a[j-1];
        a[j] = t;
    }
}

int main(int argc, char *argv[])
{
    int a[] = {13, 24, 2, 33, 12, 22, 5, 89, 85};
    int i;

    for (i = 0; i < 9; i++)
        printf("%d ", a[i]);
    printf("\n");

    shellsort(a, 9);
    for (i = 0; i < 9; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}
